/*
Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int s_length = s.length();

        struct stu_sub_string_pos {
            int start_pos;
            int end_pos;
        };
        vector<stu_sub_string_pos> vec_sub_string;

        stu_sub_string_pos temp_sub_string;
        temp_sub_string.start_pos = 0;
        temp_sub_string.end_pos = 0;

        for(int i = 1; i < s_length; ++i)
        {
            char next = s[i];
            bool has_same = false;
            int j = 0;

            for(j = temp_sub_string.start_pos; j <= temp_sub_string.end_pos; ++j)
            {
                char temp = s[j];

                if(next == temp)
                {
                    has_same = true;
                    break;
                }
            }

            if(has_same)
            {
                vec_sub_string.push_back(temp_sub_string);
                temp_sub_string.start_pos = j + 1;
                temp_sub_string.end_pos = j + 1;
                i = j + 1;
            }
            else
            {
                temp_sub_string.end_pos = i;
                if(i + 1 >= s_length)
                {
                    vec_sub_string.push_back(temp_sub_string);
                }
            }
        }

        int max_length = 1;
        if(s.empty())
        {
            max_length = 0;
        }
        if(!vec_sub_string.empty())
        {
            max_length = vec_sub_string[0].end_pos - vec_sub_string[0].start_pos + 1;
        }
        
        for(vector<stu_sub_string_pos>::iterator iter = vec_sub_string.begin(); iter != vec_sub_string.end(); ++iter)
        {
            stu_sub_string_pos temp_string = *iter;
            int temp_length = temp_string.end_pos - temp_string.start_pos + 1;

            if(max_length < temp_length)
            {
                max_length = temp_length;
            }
        }

        return max_length;
    }
};
